package com.mlh.hash;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

//给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：
//0 <= i, j, k, l < n
//nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
//输入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
//输出：2
//解释：
//两个元组如下：
//1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
//2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0
public class FourSum {
	//自己的解法和leetcode一样
	//但是细节方面没处理好，消耗时间比较久
	public int method1(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
		int n=nums1.length;
		int res=0;
		Map twoSum = findTwoSum(nums3, nums4);
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				if(twoSum.containsKey(-(nums1[i]+nums2[j]))){
					res +=(int)twoSum.get(-(nums1[i] + nums2[j]));
				}
			}
		}
		return res;
	}

	//创建一个map将另外两个数组的结果以及重复的次数记录到map中，供主方法使用
	public static Map findTwoSum(int[]nums1,int[]nums2){
		Map<Integer,Integer> map = new HashMap<>();
		int n=nums1.length;
		for(int i=0;i< n;i++){
			for(int j=0;j<n;j++){
				if(map.containsKey(nums1[i]+nums2[j])){
					map.put(nums1[i]+nums2[j],map.get(nums1[i]+nums2[j])+1);
				}else{
					map.put(nums1[i]+nums2[j],1);
				}
			}
		}
		return map;
	}
}
